|
|
Demonstrations of Jumping Automata
Růžička, Ladislav ; Kocman, Radim (referee) ; Křivka, Zbyněk (advisor)
This paper is concerned with demonstration of newly investigated jumping finite automata. Unlike conventional finite automata that read input words continuously these automatas make a jump over some symbols and from there it can read a symbol. In this paper we will be mostly focused on finding a practical algorithm for solving the membership problem. As will be shown the membership problem for jumping finite automata can be reduced to finding a non-negative integral solution to a Quantifier-Free Presburger arithmetics formula. From such formula we are able to determine whole infinite language of jumping finite automata. We will show that some subset of jumping finite automata can be solved in polynomial time. We note that formula in Presburger arithmetics can be transformed to the corresponding concurent finite automata. Unfortunately for general jumping automata finding non-negative solution is not sufficent but it can reduce search space. Other heuristics will be presented that increase the effectivity for the general jumping finite automata acceptance process.
|
|
|
Demonstrations of Jumping Automata
Růžička, Ladislav ; Kocman, Radim (referee) ; Křivka, Zbyněk (advisor)
This paper is concerned with demonstration of newly investigated jumping finite automata. Unlike conventional finite automata that read input words continuously these automatas make a jump over some symbols and from there it can read a symbol. In this paper we will be mostly focused on finding a practical algorithm for solving the membership problem. As will be shown the membership problem for jumping finite automata can be reduced to finding a non-negative integral solution to a Quantifier-Free Presburger arithmetics formula. From such formula we are able to determine whole infinite language of jumping finite automata. We will show that some subset of jumping finite automata can be solved in polynomial time. We note that formula in Presburger arithmetics can be transformed to the corresponding concurent finite automata. Unfortunately for general jumping automata finding non-negative solution is not sufficent but it can reduce search space. Other heuristics will be presented that increase the effectivity for the general jumping finite automata acceptance process.
|
|
|
Optimization of production of the nutritional products
Slámová, Dominika ; Sekničková, Jana (advisor) ; Kuncová, Martina (referee)
The theme of the thesis is to optimize the production of nutritional products of defunct company of Ing. Petra Němce. The company was engaged in production of nutritional mixtures for bakeries, pastry shops, ice cream parlours and gastronomy industry. The main objective is to create a model to find the optimal structure of production in order to maximize profit while minimizing costs and maximizing revenue. The partial task is to determine the optimum number of manufactured products and the quantity produced mixtures. The thesis describes particular solutions using the simplex method and integer linear programming. The compromise solution is obtained using multicriterial programming. Fulfilments of the set goals and their evaluation are described in the conclusion.
|
|
|
LP relaxations and pruning for characteristic imsets
Studený, Milan
The geometric approach to learning BN structure is to represent it by a certain vector; a suitable such zero-one vector is the characteristic imset, which allows to reformulate the task of finding global maximum of a score over BN structures as an integer linear programming problem. The main contribution of this report is an LP relaxation of the corresponding polytope, that is, a polyhedral description of the domain of the respective integer linear programming problem.
|
guest ::
